﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



// Condition: Write a program that sorts an array of strings using the quick sort algorithm



    class Program
    {
        static void Main(string[] args)
        {
            // Create an unsorted array of string elements
            Console.Write("Enter number of elements in string array: ");
            int N = int.Parse(Console.ReadLine());
            string[] unsorted = new string[N];
            Console.WriteLine("Enter elements of string array which are letters in english: ");
            for (int index = 0; index < N; index++)
            {
                Console.Write("element[{0}]= ", index);
                unsorted[index] = (Console.ReadLine());
            }
            Console.WriteLine();


            // Print the unsorted array
            Console.WriteLine("Unsorted array:");
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }

            Console.WriteLine();

            // Sort the array
            Quicksort(unsorted, 0, unsorted.Length - 1);

            // Print the sorted array
            Console.WriteLine(new string('-',20));
            Console.WriteLine("Sorted array:");
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }

            Console.WriteLine();
        }

        public static void Quicksort(IComparable[] elements, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = elements[(left + right) / 2];

            while (i <= j)
            {
                while (elements[i].CompareTo(pivot) < 0)
                {
                    i++;
                }

                while (elements[j].CompareTo(pivot) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    
                    IComparable tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;

                    i++;
                    j--;
                }
            }

            // Recursive 
            if (left < j)
            {
                Quicksort(elements, left, j);
            }

            if (i < right)
            {
                Quicksort(elements, i, right);
            }
        }

    }



